import java.util.Arrays;
//贪心+动态规划
public class LeetCode135 {
    public int candy(int[] ratings) {
        if (ratings.length == 0) {
            return 0;
        }
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);//初始化每个人至少有一个糖果
//        从左到右遍历
        for (int i = 1; i < candies.length; i++) {
            //确保右边评分高的孩子比左边的孩子多一颗糖果
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
//        从右到左遍历
        for (int i = ratings.length - 2; i >= 0; i--) {
            //确保左边评分高的孩子比右边的孩子多一颗糖果
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }
//        计算糖果总和
        int total = 0;
        for (int candy : candies) {
            total += candy;
        }
        return total;
    }
}
